// NC68.跳台阶/递归dp/f(n)=f(n-1)+f(n-2)
// https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
//青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上 n
//级的台阶总共有多少种跳法.先后次序不同算不同的结果 输入：2 返回值：2
//青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。
//因此答案为2
//输入：7
//返回值：21

#include <iostream>
#include <string>
using namespace std;

int jumpStep(int n) {
  if (n <= 1) {
    return 1;
  }
  return jumpStep(n - 1) + jumpStep(n - 2);
}

int jumpStep2(int target) {
  int dp[100];
  if (target <= 1) return target;
  dp[0] = 1;  // 0
  dp[1] = 1;  // 1 floor
  for (int i = 2; i <= target; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[target];
}

int main_nc68() {
  int n = jumpStep(7);
  printf("%d\n", n);
  return 0;
}
